
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

class Solution
{
    vector<string> res;
    string path;
    vector<string> nstr;

public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.empty()) return res;
        nstr = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
        dfs(digits, 0);
        return res;
    }

    void dfs(string& str, int idx)
    {
        if (path.size() == str.size())
        {
            res.push_back(path);
            return;
        }

        for (int j = 0; j < nstr[str[idx] - '0'].size(); ++j)
        {
            path += nstr[str[idx] - '0'][j];
            dfs(str, idx + 1);
            path.pop_back();
        }
    }
};